//Bptree.h

#ifndef _BPTREE_H_
#define _BPTREE_H_

#include<queue>


namespace Bpt{

    static const int M = 2;
    struct BTNode{
        int keyNum;//keyNum指key的个数或者最后一个child指针的数组下标
        int key[2 * M - 1];  //关键字数组
        struct BTNode* child[2 * M];//孩子结点数组
        /*虽然在逻辑上是两个节点数组各个元素相间分布，但是由于受到语法限制，
        **我们只能够开辟两个数组以供使用
        **对于key[i]关键字，其左子树对应左指针节点child[i]，其右子树对应右指针节点child[i+1]
        **这一点需要十分清晰 */
        bool isLeaf;
    };

    class BPTree{
        
        BTNode* root;
        //在插入时，保证pNode结点的关键字少于2*M-1个
        void InsertNonFull(BTNode* pNode, int key);
        //当child结点有2M-1个关键字时，分裂此结点
        void SplitChild(BTNode* parent, int i, BTNode* child);
        //两个关键字数量都小于M的结点合并
        void merge(BTNode* parent, BTNode* pNode1, BTNode* pNode2, int index);
        //找到比pNode结点第一个关键字小的最大的关键字，也就是前继结点
        int predecessor(BTNode* pNode);
        //找到后继结点
        int successor(BTNode* pNode);
        //pNode1向parent要一个结点key[index]，parent向pNode0要一个结点，pNode1关键字个数为M-1
        void ExchangeLeftNode(BTNode *parent, BTNode* pNode0, BTNode* pNode1, int index);
        void ExchangeRightNode(BTNode* parent, BTNode* pNode1, BTNode *pNode2, int index);
        //删除，结点关键字个数不少于M
        void RemoveNonLess(BTNode* pNode, int key);
        //磁盘的写入与读取操作
        void DiskWrite(BTNode* pNode);
        void DiskRead(BTNode *pNode);
        BTNode* Search(BTNode* pNode, int key, int &index);
    public:
        BPTree();
        ~BPTree();
        BTNode* search(int key, int &index);
        void insert(int key);
        void remove(int key);
        //按层级打印。
        void PrintRow();
    };


};


#endif //_BPTREE_H_
